package leetcode.D500.T438;

import java.util.*;

class Solution {
    // 一刷
    /*public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        Set<Character> set = new HashSet<>();
        int[] need = new int[26], window = new int[26];
        int left = 0, right = 0, valid = 0;
        for(int i=0; i<p.length(); ++i) {
            need[p.charAt(i)-'a']++;
            set.add(p.charAt(i));
        }
        int size = set.size();
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(need[c-'a'] > 0) {
                window[c-'a']++;
                if(window[c-'a'] == need[c-'a']) {
                    valid++;
                }
            }
            while(valid == size) {
                if(right - left == p.length()) {
                    result.add(left);
                }
                char d = s.charAt(left++);
                if(need[d-'a'] > 0) {
                    if(window[d-'a'] == need[d-'a']) {
                        valid--;
                    }
                    window[d-'a']--;
                }
            }
        }
        return result;
    }*/

    // 二刷
    /*public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new LinkedList<>();
        int left = 0, right = 0;
        int valid = 0, size = 0;
        int[] need = new int[26], window = new int[26];
        for(int i=0; i<p.length(); ++i) {
            char c = p.charAt(i);
            if(need[c-'a'] == 0) size++;
            need[c-'a']++;
        }
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(need[c-'a'] > 0) {
                window[c-'a']++;
                if(window[c-'a'] == need[c-'a']) {
                    valid++;
                }
            }
            while(valid == size) {
                if(right-left == p.length()) {
                    result.add(left);
                }
                char d = s.charAt(left++);
                if(need[d-'a'] > 0) {
                    if(window[d-'a'] == need[d-'a']) {
                        valid--;
                    }
                    window[d-'a']--;
                }
            }
        }
        return result;
    }*/

    // 三刷
    /*public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int left = 0, right = 0, valid = 0;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for(int i=0; i<p.length(); ++i) {
            int origin = need.getOrDefault(p.charAt(i), 0);
            need.put(p.charAt(i), origin+1);
            window.put(p.charAt(i), 0);
        }
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(need.containsKey(c)) {
                int origin = window.get(c);
                if(origin + 1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            }
            while(valid == need.size()) {
                if(right - left == p.length()) {
                    result.add(left);
                }
                char d = s.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                    window.put(d, origin-1);
                }
            }
        }
        return result;
    }*/

    // 四刷
    /*public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int left=0, right=0, valid=0;
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0)+1);
        }
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                int origin = window.getOrDefault(c, 0);
                if (origin+1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            } else {
                left = right;
                valid = 0;
                window.clear();
            }
            while (valid == need.size()) {
                if ((right-left)==p.length()) {
                    result.add(left);
                }
                char d = s.charAt(left++);
                int origin = window.get(d);
                if (origin == need.get(d)) {
                    valid--;
                }
                window.put(d, origin-1);
            }
        }
        return result;
    }*/

     // 五刷
     public List<Integer> findAnagrams(String s, String p) {
         int left = 0, right = 0, valid = 0, unique = 0;
         List<Integer> res = new ArrayList<>();
         int[] window = new int[26], need = new int[26];
         for (int i=0; i<p.length(); ++i)
             need[p.charAt(i) - 'a']++;
         for (int i=0; i<26; ++i)
             if (need[i] > 0)
                 unique++;
         while (right < s.length()) {
             char c = s.charAt(right++);
             if (window[c - 'a'] == need[c - 'a'] - 1) {
                 valid++;
             }
             window[c - 'a']++;
             while (valid == unique) {
                 if (right - left == p.length())
                     res.add(left);
                 char d = s.charAt(left++);
                 if (window[d - 'a'] == need[d - 'a']) {
                     valid--;
                 }
                 window[d - 'a']--;
             }
         }
         return res;
     }
}